public class _88 {
    static class Solution1 {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            //传统的算法，用新的数组来接受，但是，现在只能用nums1
            //如果不考虑复制最终结果的话
            // 可以考虑，从第 m 下标开始存，后n个必然先填充完
            //所以最后会变成2部分 [0,m-1] [m,m+n-1]
            //然后我们要想办法把 最终将这2部分交换变成 [m,m+n-1] + [0,m-1]
            int i = 0, j = 0;
            int idx = m % (m + n);
            while (i < m || j < n) {
                if (j >= n || (i < m && nums1[i] <= nums2[j])) {
                    nums1[idx] = nums1[i++];
                } else {
                    nums1[idx] = nums2[j++];
                }
                idx = (idx + 1) % (m + n);
            }
            //原地目前没思路，但是还有个nums2可以利用
            //将[m,m+n-1]复制到 nums2中，
            //然后nums1整体向后移动n
            //最终将 nums2复制到nums1的前 n位
            System.arraycopy(nums1, m, nums2, 0, n);
            System.arraycopy(nums1, 0, nums1, n, m);
            System.arraycopy(nums2, 0, nums1, 0, n);
        }
    }

    static class Solution2 {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            //大佬的思路
            //从右向左，将最大的直接放到当前最大索引处
            int i = m - 1;
            int j = n - 1;
            int k = m + n - 1;
            while (i >= 0 || j >= 0) {
                if (j < 0 || (i >= 0 && nums1[i] >= nums2[j])) {
                    nums1[k--] = nums1[i--];
                } else {
                    nums1[k--] = nums2[j--];
                }
            }
        }
    }

}
